/*
 * CopyRight(C) Kenbin
 */

#include "lsg_config.h"

LSG::CBuddyBit::CBuddyBit(char *buddybit, int bit_bytes)
{
    m_buddybit_total = bit_bytes * 8 / 2;

    m_total_slot_class = GetPower(m_buddybit_total);
    assert(m_total_slot_class >= 3);

    m_slot_item_count = new int[m_total_slot_class];
    m_slot_item_size = new int[m_total_slot_class];
    assert(m_slot_item_count && m_slot_item_size);

    /* class[0] have 1 slot and m_buddybit_total buddybits per slot */
    m_slot_item_count[0] = 1;
    m_slot_item_size[0] = m_buddybit_total;

    /* class[1] have 2 slot and m_buddybit_total / 2 buddybits per slot, and so on
       but all class's buddybit_total is same */
    for(int i = 1; i < m_total_slot_class; i ++)
    {
	m_slot_item_count[i] = m_slot_item_count[i-1] * 2;
	m_slot_item_size[i] = m_slot_item_size[i-1] / 2;
    }

    /* free tree and occupied tree mark the using-status of every class's every slot */
    m_free_tree = (char **)new char[sizeof(char *) * m_total_slot_class];
    m_occupied_tree = (char **)new char[sizeof(char *) * m_total_slot_class];
    assert(m_free_tree && m_occupied_tree);

    for(int i = 0; i < m_total_slot_class; i ++)
    {
	int bytes = (m_slot_item_count[i] + 7) / 8;

	m_free_tree[i] = new char[bytes];
	m_occupied_tree[i] = new char[bytes];
	assert(m_free_tree[i] && m_occupied_tree[i]);

	memset(m_free_tree[i], 0xFF, bytes);
	memset(m_occupied_tree[i], 0x0, bytes);
    }

    /* buddybit: 2 bit per block, the first tell if-used and another tell if-prev-is-used */
    m_buddybit = new char[bit_bytes];
    assert(m_buddybit);

    if(buddybit)
    {
	memcpy(m_buddybit, buddybit, bit_bytes);
	m_buddybit_alloced = flush_tree(0, m_buddybit_total);
    }
    else
    {
	memset(m_buddybit, 0, bit_bytes);
	m_buddybit_alloced = 0;
    }
}

LSG::CBuddyBit::~CBuddyBit()
{
    delete []m_slot_item_count;
    delete []m_slot_item_size;

    for(int i = 0; i < m_total_slot_class; i ++)
    {
	delete []m_free_tree[i];
	delete []m_occupied_tree[i];
    }
    delete []m_free_tree;
    delete []m_occupied_tree;

    delete []m_buddybit;
}

int LSG::CBuddyBit::Alloc(int block_count, int *byte_offset, int *bytes)
{
    *byte_offset = *bytes = 0;

    int alloc_cnt = 1;
    while(1)
    {
	if(block_count <= alloc_cnt) {
	    break;
	} else {
	    alloc_cnt *= 2;
	}
    }

    int buddybit_offset = get_free_slot_item(alloc_cnt);
    if(buddybit_offset >= 0)
    {
	flush_buddybit(buddybit_offset, alloc_cnt, 1);
	flush_tree(buddybit_offset, alloc_cnt);

	m_buddybit_alloced += alloc_cnt;

	*byte_offset = buddybit_offset / 4;
	*bytes = (buddybit_offset + alloc_cnt -1) / 4 - *byte_offset + 1;
    }

    return buddybit_offset;
}

void LSG::CBuddyBit::Free(int buddybit_offset, int *byte_offset, int *bytes)
{
    *byte_offset = *bytes = 0;

    if(buddybit_offset < 0) {
	return;
    }

    if(getbit(m_buddybit, buddybit_offset * 2) == 0 
	    || getbit(m_buddybit, buddybit_offset * 2 + 1) == 1) {
	return;
    }

    int k;
    for(k = buddybit_offset + 1; k < m_buddybit_total; k ++) {
	if(getbit(m_buddybit, k * 2 + 1) == 0) {
	    break;
	}
    }

    flush_buddybit(buddybit_offset, k - buddybit_offset, 0);
    flush_tree(buddybit_offset, k - buddybit_offset);

    m_buddybit_alloced -= k - buddybit_offset;
    *byte_offset = buddybit_offset / 4;
    *bytes = (k - 1) / 4 - *byte_offset + 1;
}

int LSG::CBuddyBit::SlotItemSize(int buddybit_offset)
{
    if(buddybit_offset < 0 || buddybit_offset >= m_buddybit_total) {
	return LSG_INVALID_BUDDYBIT_OFFSET;
    } else if(getbit(m_buddybit, buddybit_offset * 2) != 1
	    || getbit(m_buddybit, buddybit_offset * 2 + 1) != 0) {
	return LSG_INVALID_BUDDYBIT;
    }

    int end_buddybit = buddybit_offset + 1;
    while(1)
    {
	if(end_buddybit >= m_buddybit_total || getbit(m_buddybit, end_buddybit * 2) != 1
		|| getbit(m_buddybit, end_buddybit * 2 + 1) != 1) {
	    break;
	}
	end_buddybit ++;
    }

    return end_buddybit - buddybit_offset;
}

int LSG::CBuddyBit::Alloced()
{
    if(m_buddybit_alloced >= 0 && m_buddybit_alloced <= m_buddybit_total) {
	return m_buddybit_alloced;
    }

    return LSG_INVALID_BUDDYBIT_ALLOCED;
}

int LSG::CBuddyBit::get_free_slot_item(int block_count, int slot_class, int buddybit_offset)
{
    if(block_count <= 0 || GetPower(block_count) < 0) {
	return LSG_INVALID_REQUEST_BLOCK_COUNT;
    } else if(slot_class < 1 || slot_class > m_total_slot_class) {
	return LSG_INVALID_SLOT_CLASS;
    } else if(buddybit_offset < 0) {
	return LSG_INVALID_BUDDYBIT_OFFSET;
    }

    int new_buddybit_offset = -1;
    if(slot_class == m_total_slot_class)
    {
	if(block_count == 1)
	{
	    for(int i = buddybit_offset; i < buddybit_offset + 2; i ++)
	    {
		if(getbit(m_buddybit, i * 2) == 0)
		{
		    new_buddybit_offset = i;
		    break;
		}
	    }
	}
    }
    else /* class[0] ... class[m_total_slot_class - 1] */
    {
	if(block_count < m_slot_item_size[slot_class])
	{
	    for(int i = buddybit_offset; i < buddybit_offset + 2; i ++)
	    {
		if(getbit(m_occupied_tree[slot_class], i) == 0)
		{
		    new_buddybit_offset = get_free_slot_item(block_count, slot_class + 1, i * 2);
		    if(new_buddybit_offset >= 0) {
			break;
		    }
		}
	    }
	}
	else if(block_count == m_slot_item_size[slot_class])
	{
	    for(int i = buddybit_offset; i < buddybit_offset + 2; i ++)
	    {
		if(getbit(m_free_tree[slot_class], i))
		{
		    new_buddybit_offset = i;
		    break;
		}
	    }

	    if(new_buddybit_offset >= 0) {
		for(int i = slot_class; i < m_total_slot_class; i ++) {
		    new_buddybit_offset *= 2;
		}
	    }
	}
    }

    return new_buddybit_offset;
}

void LSG::CBuddyBit::flush_buddybit(int buddybit_offset, int block_count, int value)
{
    if(buddybit_offset < 0 || block_count <= 0 
	    || buddybit_offset + block_count > m_buddybit_total) {
	return;
    }

    if(block_count <= 16) /* 1,2,4,8,16 */
    {
	for(int i = buddybit_offset; i < buddybit_offset + block_count; i ++)
	{
	    setbit(m_buddybit, i * 2, value);
	    setbit(m_buddybit, i * 2 + 1, value);
	}
	setbit(m_buddybit, buddybit_offset * 2 + 1, 0);
    }
    else /* 32,64,128, ... */
    {
	int start_byte = buddybit_offset / 8 + 1;
	int end_byte = (buddybit_offset + block_count - 1) / 8;

	for(int i = buddybit_offset; i < start_byte * 8; i ++)
	{
	    setbit(m_buddybit, i * 2, value);
	    setbit(m_buddybit, i * 2 + 1, value);
	}

	memset(m_buddybit + start_byte * 2, (value ? 0xFF : 0x0), (end_byte - start_byte) * 2);

	for(int i = end_byte * 8; i < buddybit_offset + block_count; i ++)
	{
	    setbit(m_buddybit, i * 2, value);
	    setbit(m_buddybit, i * 2 + 1, value);
	}

	setbit(m_buddybit, buddybit_offset * 2 + 1, 0);
    }
}

int LSG::CBuddyBit::flush_tree(int buddybit_offset, int block_count)
{
    if(buddybit_offset < 0 || block_count <= 0 
	    || buddybit_offset + block_count > m_buddybit_total) {
	return 0;
    }

    int alloc = 0;

    int start = buddybit_offset;
    int end = buddybit_offset + block_count;

    for(int i = m_total_slot_class - 1; i >= 0; i --)
    {
	if(start % 2 == 1) {
	    start --;
	}
	if(end % 2 == 1) {
	    end ++;
	}
	if(end == start) {
	    end += 2;
	}

	if(i == m_total_slot_class - 1)
	{
	    /* handle 2 blocks(2 buddybits=4 bits) per for */
	    for(int k = start; k < end; k += 2)
	    {
		int B1 = getbit(m_buddybit, k * 2); /* current block if-used */
		int B2 = getbit(m_buddybit, (k + 1) * 2); /* prev block if-used */

		setbit(m_free_tree[i], k / 2, B1 == 0 & B2 == 0);
		setbit(m_occupied_tree[i], k / 2, B1 & B2);

		alloc += B1 + B2;
	    }
	}
	else
	{
	    /* handle 2 slots per for */
	    for(int k = start; k < end; k += 2)
	    {
		int B1 = getbit(m_free_tree[i+1], k); /* left child slot if-free */
		int B2 = getbit(m_free_tree[i+1], k + 1); /* right child slot if-free */
		setbit(m_free_tree[i], k / 2, B1 && B2);

		B1 = getbit(m_occupied_tree[i+1], k); /* left child slot if-occupied */
		B2 = getbit(m_occupied_tree[i+1], k + 1); /* right child slot if-occupied */
		setbit(m_occupied_tree[i], k / 2, B1 && B2);
	    }
	}

	start /= 2;
	end /= 2;
    }

    return alloc;
}

inline int LSG::CBuddyBit::getbit(char *bit, int bit_offset)
{
    bit += bit_offset / 8;
    return (*bit >> (bit_offset % 8)) & 0x01;
}

inline void LSG::CBuddyBit::setbit(char *bit, int bit_offset, int value)
{
    bit += bit_offset / 8;
    char c = (0x01 << (bit_offset % 8));
    if(value) {
	*bit |= c;
    } else {
	*bit &= ~c;
    }
}

void LSG::CBuddyBit::PrintInfo()
{
    printf("[buddybit]\n");
    printf("buddybit_total\tbuddybit_alloced\n");
    printf("%d\t\t%d\n",m_buddybit_total, m_buddybit_alloced);
    for(int c = 0, i = 0; i < m_buddybit_total; i ++)
    {
	printf("%d%d", getbit(m_buddybit, i * 2), getbit(m_buddybit, i * 2 + 1));

	c ++;
	if(c % 40 == 0) {
	    printf("\n");
	}
    }
    printf("\n");
    for(int c = 0, i = 0; i < m_buddybit_total; i ++)
    {
	if(getbit(m_buddybit, i * 2 + 1)) {
	    printf("-");
	} else if(getbit(m_buddybit, i * 2)) {
	    printf("1");
	} else {
	    printf("0");
	}

	c ++;
	if(c % 80 == 0) {
	    printf("\n");
	}
    }

    printf("\n\n");

    printf("[tree]\n");
    printf("slot_class\tslot_item_count\tslot_item_size\n");
    for(int i = 0; i < m_total_slot_class; i ++) {
	printf("%d\t\t%d\t\t%d\n", i, m_slot_item_count[i], m_slot_item_size[i]);
    }

    printf("slot_class\tfree_tree\n");
    for(int i = 0; i < m_total_slot_class; i ++) {
	printf("%d\t\t", i);
	for(int k = 0; k < m_slot_item_count[i]; k ++) {
	    printf("%d", getbit(m_free_tree[i], k));
	}
	printf("\n");
    }

    printf("slot_class\toccupied_tree\n");
    for(int i = 0; i < m_total_slot_class; i ++) {
	printf("%d\t\t", i);
	for(int k = 0; k < m_slot_item_count[i]; k ++) {
	    printf("%d", getbit(m_occupied_tree[i], k));
	}
	printf("\n");
    }
}
